package leetcode每日一题;

import java.util.HashMap;

/**
 * 1. 问题描述
 *      n块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。
 *      如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。
 *      给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。
 *
 * 2. 算法分析
 *      并查集实现
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 移除最多同行或者同行列的石头 {
    // 定义并查集
    class UnionFind {
        HashMap<Integer,Integer> map; // 代替root数组
        int connectionCounts; // 连通分量的个数

        public UnionFind() {
            map = new HashMap<>();
            connectionCounts = 0;
        }

        public int getCount() {
            return connectionCounts;
        }

        public int find(int x) {
            // 1. 判断x是否出现在map中
            if(!map.containsKey(x)) {
                map.put(x,x);
                connectionCounts++;
            }

            // 2. 判断当前x的父节点是否为自己
            if(x != map.get(x)) {
                map.put(x,find(map.get(x)));
            }
            return map.get(x);
        }

        public void union(int x,int y) {
            int rootX = find(x);
            int rootY = find(y);
            if(rootX != rootY) {
                map.put(rootY,rootX);
                connectionCounts--;
            }
        }
    }

    public int removeStones(int[][] stones) {
        UnionFind uf = new UnionFind();
        for(int[] stone : stones) {
            uf.union(stone[0] + 10001, stone[1]);
        }
        return stones.length - uf.getCount();
    }
}
